package com.example.myletcodelearing.queue

/**
 * @author tgw
 * @date 2022/8/5
 * @describe
 */


fun main(array: Array<String>) {
    println("队列的实现")
    val test = QueueTest()
    test.inQueue(0)
    test.outQueue()
    test.inQueue(1)
    test.inQueue(2)
    test.inQueue(3)
    test.inQueue(4)
    test.outQueue()
    test.inQueue(5)
//    test.printValue()

//    println("循环队列的实现")
//    val test1 = CycleQueueTest()
//    test1.inQueue(0)
//    test1.outQueue()
//    test1.inQueue(1)
//    test1.inQueue(2)
//    test1.inQueue(3)
//    test1.inQueue(4)
//    test1.outQueue()
//    test1.outQueue()
//    test1.outQueue()
//    test1.outQueue()
//    test1.inQueue(5)
//    test1.inQueue(6)
//    test1.outQueue()
//    test1.outQueue()
//    test1.outQueue()
//    test1.printValue()


    println("循环队列的实现")
    val test1 = CycleQueueTest()
    test1.inQueue1(0)
    test1.outQueue1()
    test1.inQueue1(1)
    test1.inQueue1(2)
    test1.inQueue1(3)
    test1.inQueue1(4)
//    test1.outQueue1()
    test1.inQueue1(5)
    test1.printValue()
    test1.outQueue1()
    test1.outQueue1()
    test1.inQueue1(6)
    test1.inQueue1(7)
    test1.inQueue1(8)
    test1.outQueue1()
    test1.inQueue1(9)
    test1.outQueue1()
    test1.outQueue1()
    test1.outQueue1()
    test1.outQueue1()
    test1.outQueue1()
    test1.outQueue1()
    test1.inQueue1(1)
    test1.inQueue1(2)
    test1.inQueue1(3)
    test1.inQueue1(4)
    test1.inQueue1(5)
    test1.inQueue1(6)
    test1.printValue()
//    test1.printValue()

    println()
    println("链表队列的实现")
    val test3 = LinkQueueTest()
    test3.inQueue(0)
    test3.inQueue(1)
    test3.printValue()
    println("出队${test3.outQueue().toString()}")
    println("出队${test3.outQueue().toString()}")
    println("出队${test3.outQueue().toString()}")

    test3.inQueue(2)
    println("出队${test3.outQueue().toString()}")
    test3.inQueue(3)

    test3.printValue()
}

/**
 *普通队列
 */
class QueueTest {
    val queueSize = 5
    var front: Int = -1
    var rear: Int = -1

    val datas = Array<Int?>(queueSize) { i -> null }

    fun inQueue(value: Int) {
        if (rear >= queueSize - 1) {
            println("已经到达了队尾：$rear---值：$value 无法添加")
            return
        }
        rear++
        datas[rear] = value
    }


    fun outQueue(): Int? {
        if (front >= rear) {
            println("出队到了最后一个元素front：$front---rear：$rear")
            return null
        }
        front++
        var value = datas[front]
        datas[front] = null
        return value
    }

    fun printValue() {
        datas.forEach {
            print("打印值:$it")
        }
        print("打印队指针:元素front：$front---rear：$rear")
    }
}

/**
 *循环队列
 */
class CycleQueueTest {
    val queueSize = 5
    var front: Int = -1
    var rear: Int = -1

    val datas = Array<Int?>(queueSize) { i -> null }

    fun inQueue(value: Int) {
        if (rear == queueSize - 1) {
            if (rear - front < queueSize) {
                rear = -1
            } else {
                println("已经到达了队尾：$rear---值：$value 无法添加")
                return
            }
        }
        rear++
        datas[rear] = value
    }


    fun inQueue1(value: Int) {
        if (rear != -1 && front == rear && datas[(rear + 1) % queueSize] != null) {
            println("已经到达了队尾：$rear---值：$value 无法添加")
            return
        }
        //防止总是入队
        if (front == -1 && rear >= queueSize - 1) {
            println("已经到达了队尾：$rear---值：$value 无法添加")
            return
        }
        rear = (rear + 1) % queueSize
        datas[rear] = value
    }

    fun outQueue(): Int? {
        if (front == rear) {
            println("出队到了最后一个元素front：$front---rear：$rear")
            return null
        }
        if (front == queueSize - 1) {
            front = -1
        }
        front++
        var value = datas[front]
        datas[front] = null
        return value
    }

    fun outQueue1(): Int? {
        if (front == rear && datas[(rear + 1) % queueSize] == null) {
            println("出队到了最后一个元素front：$front---rear：$rear")
            return null
        }

        front = (front + 1) % queueSize
        var value = datas[front]
        datas[front] = null
        return value
    }

    fun printValue() {
        println()
        datas.forEach {
            print("打印值:$it")
        }
        print("打印队指针:元素front：$front---rear：$rear")
    }
}


/**
 *链表队列
 */
class LinkQueueTest {

    class LinkQueueNode {
        var value: Int? = null

        var next: LinkQueueNode? = null

        override fun toString(): String {
            return "LinkQueueNode(value=$value, next=$next)"
        }

    }
    var rear: LinkQueueNode? = null
    var front: LinkQueueNode? = null

    var datas: LinkQueueNode? = LinkQueueNode().apply {
        value = -1
        next = LinkQueueNode()
    }


    val size = 0


    fun inQueue(value: Int) {
        val node = LinkQueueNode()

        var data = datas
        while (data != null) {
            if (data.value == null) {
                data.value = value
                data.next = node
                rear = data
                break
            }
            data = data.next
        }
    }


    fun outQueue():LinkQueueNode?{
        if (front==rear) {
            println("队里没有数据${datas.toString()}")
            return null
        }
        var data = datas
        if (data?.next != null){
            front = data?.next
            datas?.next = front?.next
        }
        return front
    }

    fun printValue() {
        println()
        var endNode = datas?.next
        while (endNode?.value != null) {
            println("打印值:${endNode.value}")
            endNode = endNode.next
        }

    }
}